"""
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import defaultdict
from binarytree import Node

TreeNode = Node


class Solution:
    def __init__(self):
        ...
        self._count = 0
        # 记录所有前缀和出现的次数
        self.presumlist = defaultdict(int)
        self.presumlist[0] += 1
        # 记录当前前缀和
        self.presum = 0

    def pathSum(self, root: TreeNode, targetSum: int) -> int:

        if not root:
            return 0
        # 计算到当前节点的前缀和
        self.presum += root.val
        # 更新前缀和的列表
        self.presumlist[self.presum] += 1
        # 查找前缀和列表，更新结果
        self._count += self.presumlist[self.presum - targetSum]
        print(self.presumlist)

        self.pathSum(root.left, targetSum)
        self.pathSum(root.right, targetSum)

        self.presumlist[self.presum] -= 1
        self.presum -= root.val

        return self._count

    # def helper(self, root: TreeNode, targeSum: int) -> int:
    #     if not root:
    #         return 0
    #     if root.val == targetSum:
    #         self._count += 1
    #     self.helper(root.left, targetSum - root.val)
    #     self.helper(root.right, targetSum - root.val)


if __name__ == "__main__":
    node1 = Node(5)
    node2 = Node(3)
    node3 = Node(5)
    node4 = Node(5)
    node1.left = node2
    node2.left = node3
    node2.right = node4

    print(node1)
    my_solution = Solution()
    print(my_solution.pathSum(node1, 0))
